#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <map>
#include <tuple>
using namespace std;
#define int long long



//int a, b, n;
//int s[1005][1005];
//int mx[1005][1005];
//int mi[1005][1005];
//
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> a >> b >> n;
//	for (int i = 1; i <= a; i++) {
//		for (int j = 1; j <= b; j++) {
//			cin >> s[i][j];
//		}
//	}
//
//	for (int i = 1; i <= a; i++) {
//		deque<int> qmx;
//		deque<int> qmi;
//		for (int j = 1; j <= b; j++) {
//			while (!qmx.empty() && s[i][qmx.back()] <= s[i][j])qmx.pop_back();
//			while (!qmi.empty() && s[i][qmi.back()] >= s[i][j])qmi.pop_back();
//			qmx.push_back(j);
//			qmi.push_back(j);
//			if (qmx.front() + n == j) {
//				qmx.pop_front();
//			}
//			if (qmi.front() + n == j) {
//				qmi.pop_front();
//			}
//			if (j >= n) {
//				mx[i][j - n + 1] = s[i][qmx.front()];
//				mi[i][j - n + 1] = s[i][qmi.front()];
//			}
//		}
//	}
//	int ans = 1e9;
//	for (int i = 1; i <= b - n + 1; i++) {
//		deque<int> qmx;
//		deque<int> qmi;
//		for (int j = 1; j <= a; j++) {
//			while (!qmx.empty() && mx[qmx.back()][i] <= mx[j][i])qmx.pop_back();
//			while (!qmi.empty() && mi[qmi.back()][i] >= mi[j][i])qmi.pop_back();
//			qmx.push_back(j);
//			qmi.push_back(j);
//			if (qmx.front() + n == j) {
//				qmx.pop_front();
//			}
//			if (qmi.front() + n == j) {
//				qmi.pop_front();
//			}
//			if (j >= n) {
//				mx[j - n + 1][i] = mx[qmx.front()][i];
//				mi[j - n + 1][i] = mi[qmi.front()][i];
//				ans = min(ans, mx[j - n + 1][i] - mi[j - n + 1][i]);
//			}
//		}
//	}
//	cout << ans << '\n';
//	return 0;
//}

//int t, x, y;
//
//void solve() {
//	int ans = 0;
//	cin >> x >> y;
//	ans += y / 2;
//	int tmp = ans * 7;
//	y %= 2;
//	ans += y;
//	tmp += y*11;
//	if (tmp < x) {
//		x -= tmp;
//		ans += x / 15;
//		ans += x % 15 == 0 ? 0 : 1;
//	}
//	cout << ans << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}

//
//int t;
//void solve() {
//	string s;
//	int n;
//	cin >> n;
//	cin >> s;
//	string b;
//	int a[26] = {0};
//	for (auto c : s) {
//		a[c - 'a']++;
//	}
//	for (int i = 0; i <= 25; i++) {
//		if (a[i]) {
//			char c = i + 'a';
//			b += c;
//		}
//	}
//	int l = 0, r = b.size() - 1;
//	while (l < r) {
//		for (int i = 0; i <= n - 1; i++) {
//			if (s[i] == b[l]) {
//				s[i] = b[r];
//			}
//			else if (s[i] == b[r]) {
//				s[i] = b[l];
//			}
//		}
//		l++;
//		r--;
//	}
//	cout << s << '\n';
//}
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//int t;
//void solve() {
//	int n;
//	string s;
//	string ans;
//	cin >> n >> s;
//	unordered_map<char, int> mp;
//	unordered_map<char, int>cnt;
//	int hx=0, hy=0, rx=0, ry=0;
//	for (int i = 0; i < n; i++) {
//		mp[s[i]]++;
//	}
//	int cntr = 0, cnth = 0;
//	for (int i = 0; i < n; i++) {
//		if (s[i]=='E'||s[i]=='W') {
//			if (cnt[s[i]]++ < mp[s[i]]/2) {
//				ans += 'R';
//				if (s[i] == 'E')
//					rx += 1;
//				else
//					rx -= 1;
//				cntr++;
//
//			}
//			else {
//				ans += 'H';
//				if (s[i] == 'E')
//					hx += 1;
//				else
//					hx -= 1;
//
//				cnth++;
//			}
//		}
//		else {
//			if (cnt[s[i]]++ < mp[s[i]]/2) {
//				ans += 'H';
//				if (s[i] == 'N')
//					hy += 1;
//				else
//					hy -= 1;
//				cnth++;
//			}
//			else {
//				ans += 'R';
//				if (s[i] == 'N')
//					ry += 1;
//				else
//					ry -= 1;
//				cntr++;
//			}
//		}
//	}
//	if (abs(cntr - cnth) % 2||cntr==0||cnth==0||hx!=rx||hy!=ry) {
//		cout << "NO\n";
//	}
//	else {
//		cout << ans << '\n';
//	}	
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}
//int t;
//int m, x;
//int cost[55], happy[55];
//int dp[55][55][55];
//int money;
//void solve() {
//	cin >> m >> x;
//	for (int i = 1; i <= m; i++) {
//		cin >> cost[i] >> happy[i];
//	}
//	for (int i = 1; i <= m; i++) {
//		for(int j=1;j<=m;j++)
//	}
//	cout << dp[m][m][m];
//
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}


//
//int n, a[200005];
//void solve() {
//	cin >> n;
//	for (int i = 0; i <n; i++) {
//		cin >> a[i];
//	}
//	map<tuple<int, int, int>, int>mp;
//	int ans = 0;
//	int x = 0, y = 0;
//	for (int i = 0; i < n - 2; i++) {
//		mp[{a[i], a[i + 1], a[i + 2]}]++;
//		mp[{0, a[i + 1], a[i + 2]}]++;
//		mp[{a[i], 0, a[i + 2]}]++;
//		mp[{a[i], a[i + 1], 0}]++;
//		ans += mp[{0, a[i + 1], a[i + 2]}] + mp[{a[i], 0, a[i + 2]}] + mp[{a[i], a[i + 1], 0}] - 3;
//		ans -= (mp[{a[i], a[i + 1], a[i + 2]}] - 1) * 3;
//	}
//	cout << ans << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}

int C[500005];


signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	for (int i = 2; i <= 500005; i++) {

	}

	return 0;
}
